package com.desire.homework;


import java.util.Arrays;

/**
 * 平均性能为O(n^2)的有：直接插入排序，选择排序，冒泡排序
 * 平均性能为O(nlogn)的有：快速排序，归并排序，希尔排序，堆排序。其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。
 * <p>
 * 插入排序，冒泡排序，二叉树排序，归并排序都是稳定的，选择排序，希尔排序，快速排序，堆排序是不稳定的
 *
 * @author desire
 */
public class _15_排序工具类 {
    public static void main(String[] args) {
        int[] array = new int[]{6, 2, 60, 5, 4, 6, 12, 84, 2, 54, 0};
        bucketSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    /**
     * 桶排序,是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
     * <p>
     * 桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序
     * (有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)
     *
     * @param array
     */
    public static void bucketSort(int[] array) {
        int n = array.length;
        int[][] bask = new int[10][n];
        int[] index = new int[10];
        int max = Integer.MIN_VALUE;
        for (int datum : array) {
            max = Math.max(max, (Integer.toString(datum).length()));
        }
        StringBuilder str;
        for (int i = max - 1; i >= 0; i--) {
            for (int datum : array) {
                str = new StringBuilder();
                if (Integer.toString(datum).length() < max) {
                    str.append("0".repeat(Math.max(0, max - Integer.toString(datum).length())));
                }
                str.append(datum);
                bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = datum;
            }
            int pos = 0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < index[j]; k++) {
                    array[pos++] = bask[j][k];
                }
            }
            for (int x = 0; x < 10; x++) {
                index[x] = 0;
            }
        }
    }


    /**
     * 计数排序,计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
     * 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
     * <p>
     * （1）找出待排序的数组中最大和最小的元素
     * （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
     * （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
     * （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
     *
     * @param array
     * @return 排序好的数组
     */
    public static int[] countSort(int[] array) {
        int[] b = new int[array.length];
        int max = array[0], min = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //这里k的大小是要排序的数组中，元素大小的极值差+1
        int k = max - min + 1;
        int[] c = new int[k];
        for (int j : array) {
            //优化过的地方，减小了数组c的大小
            c[j - min] += 1;
        }
        for (int i = 1; i < c.length; ++i) {
            c[i] = c[i] + c[i - 1];
        }
        for (int i = array.length - 1; i >= 0; --i) {
            //按存取的方式取出c的元素
            b[--c[array[i] - min]] = array[i];
        }
        return b;
    }


    /**
     * !!!数组内不能有负数!!!
     * <p>
     * 基数排序,用于大量数，很长的数进行排序时
     * (基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。)
     * <p>
     * 将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
     * 将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
     *
     * @param array
     * @return 一个排序好的 没有负数的 数组
     */
    public static int[] radixSort(int[] array) {
        //获取 最大值
        int maxValue = array[0];
        for (int value : array) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        //获取最大的数有多少位
        if (maxValue == 0) {
            return new int[]{};
        }
        int lenght = 0;
        for (long temp = maxValue; temp != 0; temp /= 10) {
            lenght++;
        }
        int k = 0;
        int n = 1;
        //控制键值排序依据在哪一位
        int m = 1;
        //数组的第一维表示可能的余数0-9
        int[][] temp = new int[10][array.length];
        //数组order[i]用来表示该位是i的数的个数
        int[] order = new int[10];
        while (m <= lenght) {
            for (int value : array) {
                int lsd = ((value / n) % 10);
                temp[lsd][order[lsd]] = value;
                order[lsd]++;
            }
            for (int i = 0; i < 10; i++) {
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        array[k] = temp[i][j];
                        k++;
                    }
                }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
        return array;
    }


    public static int[] mergeSort(int[] array) {
        return mergeSort(array, 0, array.length - 1);
    }

    /**
     * 归并排序,速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。
     * (速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列)
     * <p>
     * 1.选择相邻两个数组成一个有序序列。
     * 2.选择相邻的两个有序序列组成一个有序序列。
     * 3.重复第二步，直到全部组成一个有序序列。
     * <p>
     * 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
     * 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
     * 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
     * 重复步骤3直到某一指针超出序列尾
     * 将另一序列剩下的所有元素直接复制到合并序列尾
     *
     * @param array
     */
    public static int[] mergeSort(int[] array, int left, int right) {
        if (left == right) {
            return new int[]{array[left]};
        }
        int mid = left + (right - left) / 2;
        // 左有序数组
        int[] leftArr = mergeSort(array, left, mid);
        // 右有序数组
        int[] rightArr = mergeSort(array, mid + 1, right);
        // 新有序数组
        int[] newArray = new int[leftArr.length + rightArr.length];
        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newArray[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length) {
            newArray[m++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            newArray[m++] = rightArr[j++];
        }
        return newArray;
    }

    public static int[] quickSort(int[] array) {
        return quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序,要求时间最快时。
     * <p>
     * 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
     * 递归的将p左边和右边的数都按照第一步进行，直到不能递归。
     *
     * @param array
     * @param leftIndex
     * @param rightIndex
     * @return 排序的数组
     */
    public static int[] quickSort(int[] array, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return new int[]{};
        }
        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = array[left];
        //从左右两边交替扫描，直到left = right
        while (left < right) {
            while (right > left && array[right] >= key) {
                //从右往左扫描，找到第一个比基准值小的元素
                right--;
            }
            //找到这种元素将arr[right]放入arr[left]中
            array[left] = array[right];
            while (left < right && array[left] <= key) {
                //从左往右扫描，找到第一个比基准值大的元素
                left++;
            }
            //找到这种元素将arr[left]放入arr[right]中
            array[right] = array[left];
        }
        //基准值归位
        array[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(array, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(array, right + 1, rightIndex);
        return array;
    }


    /**
     * 堆排序,对简单选择排序的优化。
     * <p>
     * 1.将序列构建成大顶堆。
     * 2.将根节点与最后一个节点交换，然后断开最后一个节点。
     * 3.重复第一、二步，直到所有节点断开。
     *
     * @param array
     * @return
     */
    public static int[] heapsort(int[] array) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(array, array.length);
        int len = arr.length;
        buildMaxHeap(arr, len);
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    public static void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    public static void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static int[] simpleSort(int[] array) {
        return simpleSort(array, true);
    }

    /**
     * 简单选择排序,常用于取序列中最大最小的几个数时。
     * (如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)
     * 1.遍历整个序列，将最小的数放在最前面。
     * 2.遍历剩下的序列，将最小的数放在最前面。
     * 3.重复第二步，直到只剩下一个数。
     * <p>
     * 1.首先确定循环次数，并且记住当前数字和当前位置。
     * 2.将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。
     * 3.比对完成后，将最小的值与第一个数的值交换。
     * 4.重复2、3步
     * <p>
     * 简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，
     * 直到所有元素排完为止，简单选择排序是不稳定排序。
     *
     * @param array
     * @param sort
     * @return 排序后的数组
     */
    public static int[] simpleSort(int[] array, boolean sort) {
        int temp = 0, max;
        if (sort) {
            for (int i = 0; i < array.length - 1; i++) {
                max = i;
                for (int j = i + 1; j < array.length; j++) {
                    if (array[max] > array[j]) {
                        max = j;
                    }
                }
                temp = array[max];
                array[max] = array[i];
                array[i] = temp;
            }
            return array;
        } else {
            for (int i = 0; i < array.length - 1; i++) {
                max = i;
                for (int j = i + 1; j < array.length; j++) {
                    if (array[max] < array[j]) {
                        max = j;
                    }
                }
                temp = array[max];
                array[max] = array[i];
                array[i] = temp;
            }
            return array;
        }
    }


    public static int[] shellSort(int[] array) {
        return shellSort(array, true);
    }

    /**
     * 希尔排序(缩小增量排序,直接插入排序的改进),参数 sort 可传 true(默认正序) false(倒序)
     * 希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；
     * 然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束
     * (对于直接插入排序问题,数据量巨大时)
     * <p>
     * 1.将数的个数设为n，取奇数k=n/2，将下标差值为k的书分为一组，构成有序序列。
     * 2.再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。
     * 3.重复第二步，直到k=1执行简单插入排序。
     * <p>
     * 1.首先确定分的组数。
     * 2.然后对组中元素进行插入排序。
     * 3.然后将length/2，重复1,2步，直到length=0为止。
     *
     * @param array
     * @param sort
     * @return 排序后的数组
     */
    public static int[] shellSort(int[] array, boolean sort) {
        if (sort) {
            for (int gap = array.length / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < array.length; i++) {
                    int j = i;
                    int temp = array[j];
                    if (array[j] < array[j - gap]) {
                        while (j - gap >= 0 && temp < array[j - gap]) {
                            array[j] = array[j - gap];
                            j -= gap;
                        }
                        array[j] = temp;
                    }
                }
            }
            return array;
        } else {
            for (int gap = array.length / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < array.length; i++) {
                    int j = i;
                    int temp = array[j];
                    if (array[j] > array[j - gap]) {
                        while (j - gap >= 0 && temp > array[j - gap]) {
                            array[j] = array[j - gap];
                            j -= gap;
                        }
                        array[j] = temp;
                    }
                }
            }
            return array;
        }
    }

    public static int[] bubbleSort(int[] array) {
        return bubbleSort(array, true);
    }

    /**
     * 冒泡排序, 参数 sort 可传 true(默认正序) false(倒序)
     * 一般不用。
     * <p>
     * 1.将序列中所有元素两两比较，将最大的放在最后面。
     * 2.将剩余序列中所有元素两两比较，将最大的放在最后面。
     * 3.重复第二步，直到只剩下一个数。
     * <p>
     * 1.设置循环次数。
     * 2.设置开始比较的位数，和结束的位数。
     * 3.两两比较，将最小的放到前面去。
     * 4.重复2、3步，直到循环次数完毕
     * <p>
     * 冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，
     * 这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序
     *
     * @param array
     * @param sort
     * @return 排序后的数组
     */
    public static int[] bubbleSort(int[] array, boolean sort) {
        //定义一个临时存储变量  和  一个循环的标志
        int temp;
        boolean flag = true;
        if (sort) {
            // 冒泡的趟数, n-1 趟
            for (int i = 0; i < array.length - 1; i++) {
                flag = false;
                for (int j = 0; j < array.length - i - 1; j++) {
                    if (array[j + 1] < array[j]) {
                        temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                        flag = true;
                    }
                }
                if (!flag) {
                    break;
                }
            }
            return array;
        } else {
            for (int i = 0; i < array.length - 1; i++) {
                flag = false;
                for (int j = 0; j < array.length - i - 1; j++) {
                    if (array[j + 1] > array[j]) {
                        temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                        flag = true;
                    }
                }
                if (!flag) {
                    break;
                }
            }
            return array;
        }
    }

    public static int[] insertionSort(int[] array) {
        return insertionSort(array, true);
    }

    /**
     * 直接插入排序, 参数 sort 可传 true(默认正序) false(倒序)
     * 把新的数据插入到已经排好的数据列中
     * <p>
     * 1.将第一个数和第二个数排序，然后构成一个有序序列
     * 2.将第三个数插入进去，构成一个新的有序序列。
     * 3.对第四个数、第五个数……直到最后一个数，重复第二步。
     * <p>
     * 1.首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
     * 2.设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
     * 3.从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
     * 4.将当前数放置到空着的位置，即j+1。
     * <p>
     * 直接插入排序基本思想是每一步将一个待排序的记录，
     * 插入到前面已经排好序的有序序列中去，直到插完所有元素为止
     *
     * @param array
     * @param sort
     * @return 排序后的数组
     */
    public static int[] insertionSort(int[] array, boolean sort) {
        int temp = 0, j;

        if (sort) {
            for (int i = 1; i < array.length; i++) {
                if (array[i - 1] > array[i]) {
                    temp = array[i];
                    j = i;
                    while (j > 0 && array[j - 1] > temp) {
                        array[j] = array[j - 1];
                        j--;
                    }
                    array[j] = temp;
                }
            }
            return array;
        } else {
            for (int i = 1; i < array.length; i++) {
                if (array[i - 1] < array[i]) {
                    temp = array[i];
                    j = i;
                    while (j > 0 && array[j - 1] < temp) {
                        array[j] = array[j - 1];
                        j--;
                    }
                    array[j] = temp;
                }
            }
            return array;
        }
    }
}

